package com.explorati.LeetCode88.mergesortarray;

/**
 * 改进三：不用开辟任何空间，直接在Nums1中操作
 * 思想：若nums1的最大元素大于num2中的最大元素，则num1的最后一个位置放入num1的元素，否则放入nums2的元素
 * 放入之后，最后一个位置向前移，这样操作之后，若nums2没有元素剩余(即j==0)，那么nums1中的元素已经按从小到大排列了
 * 如果nums2中有元素剩余，那么nums1中还没排完序，继续将nums2中的元素放入nums1中
 * 
 * @author explorati
 *
 */
public class Solution2 {
	public static void merge(int[] nums1, int m, int[] nums2, int n) {
		// 指向nums1中最大元素位置
		int i = m - 1;
		// 指向num2中最大元素位置
		int j = n - 1;
		// num1和nums2最大元素比完之后大的元素放的位置
		int k = nums1.length - 1;
		// 若都大于零，即都有排的元素，没有一方已经全部放入num1中
		while (i >= 0 && j >= 0) {
			if (nums1[i] > nums2[j]) {
				nums1[k--] = nums1[i--];
			} else {
				nums1[k--] = nums2[j--];
			}
		}
		// 将nums2中剩余为放入nums1中的元素放入其中
		while (j >= 0) {
			nums1[k--] = nums2[j--];
		}
	}
}
